The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
Computing systems perform a large number of tasks using a finite number of resources. Rather than naively perform each task in the order in which it was received, a computing device may implement various resource scheduling and management techniques to ensure that the tasks are performed in an order that achieves various important objectives, such as ensuring that high priority tasks are performed within a certain amount of time or guaranteeing a minimum level of performance with respect to tasks that pertain to a certain requestor.
In some systems, tasks may be classified according to various classifications. A task management system may enforce various rules with respect to these classifications, such as ensuring that the rate at which the tasks for a given classification are performed conforms to certain minimum or maximum requirements. Bucket-based mechanisms are well-suited for enforcing such rules.
One type of bucket-based mechanism is a token bucket. One example use of a token bucket is as follows. Each classification of tasks is assigned to a different “bucket,” which stores, conceptually, an amount of “tokens” for the classification. Before performing a task, the classification of the task is determined. An amount of tokens needed for the task (e.g. corresponding to a size of a resource needed for the task) is also determined. The bucket associated with the task is consulted to determine whether there are enough tokens in the bucket to perform the task. If so, then the tokens are removed from the bucket, and the task is “conformant” and performed. If there are not enough tokens, then the task is “non-conformant” and various non-conforming responses are possible, depending on the embodiment. These responses may include, for example, waiting to perform the task, skipping the task, lowering the priority of the task, and so forth. The bucket is replenished by adding new tokens periodically according to some replenishment rate, which can be adjusted for various purposes.
Another type of bucket-based mechanism is a leaky bucket. One example use of a leaky bucket is as follows. As with the token bucket, each classification is assigned to a different bucket. Each bucket is also assigned a capacity (i.e. maximum size). Again, the classification of the task is determined. Again, an amount of resources (hereinafter also referred to as tokens) needed for the task is determined. However, instead of removing the tokens from the bucket, the tokens are added to the bucket, so long as the bucket does not exceed the capacity of the bucket (i.e. is conformant). If the capacity of the bucket will be exceeded, then the task is in non-conformant, and the same non-conforming responses are possible. The bucket “leaks”—i.e. tokens are removed from the bucket—at a defined leak rate, which again can be adjusted for various purposes.
Of course, a number of variations on the above examples are possible, and the described techniques are relevant to bucket-based mechanisms in general rather than any specific algorithm.
Bucket-based mechanisms are often used for traffic management in networking devices, such as switches and routers. In this context, the tasks at issue typically relate to the processing of packets, cells, datagrams, or other data structures (collectively referred to herein as “messages”). For instance, the tasks may be sending or routing a message, inspecting a message, manipulating a message, and so forth. The classifications are referred to herein as traffic action control groups. Messages may be assigned to different traffic action control groups based on any suitable criteria, including, without limitation, labels, destination or sending addresses, destination or sending ports, destination or sending services, traffic classes, applications, protocols, and so forth. The networking device may employ various traffic management rules or algorithms to ensure that messages pertaining to certain traffic action control groups have certain qualities of service, such as guaranteed minimum or maximum sending rates.
For instance, traffic shaping is a network traffic management technique in which the processing of certain messages may be delayed to bring them into compliance with some guaranteed performance standard. As another example, traffic policing is a network traffic management technique that involves discarding and/or marking certain messages that do not comply with a contract or some other guarantee. Token buckets or leaky buckets are often utilized for these and other traffic management techniques.
For certain types of usage patterns in certain types of computer systems, such as with respect to traffic management in network switching devices, the frequency with which buckets must be updated requires that the memory used to store the buckets be capable of sustaining a high read and write rate. For instance, multi-ported memory is often required in such contexts, which can be of relatively high cost and reduced operating rate. Moreover, as the number of classifications to which a task may be assigned increases, the memory requirements also increase.